#
# fusion.core.item
#
# Copyright 2007 Helsinki Institute for Information Technology
# and the authors.
#
# Authors: Ken Rimey <rimey@hiit.fi>
#

# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation files
# (the "Software"), to deal in the Software without restriction,
# including without limitation the rights to use, copy, modify, merge,
# publish, distribute, sublicense, and/or sell copies of the Software,
# and to permit persons to whom the Software is furnished to do so,
# subject to the following conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

'''
Encoding for Tamper-Resistant Sharing

ETRS organizes data as Items.  Each Item has a canonical serialization
as a canonical s-expression, which is a particular encoding for lists
of strings and nested lists (see fusion.lib.sexp).  The first element
of the list representation of an Item is its type.  The last element
is a signature, which is computed over the canonical s-expression for
the same list minus the signature.

All of the elements that are combined to produce the canonical
serialization are strings.  Components that are themselves serialized
as canonical s-expressions are serialized before being used to
construct the canonical serialization of the Item.  (Even when an
element is itself a list, we very often want to be able to deal with
it as a string.)

Each Item has a 20-byte ID.  This is simply the SHA-1 hash of the
canonical serialization.

The currently supported item types are as follows.

["root" public_key salt sig]

Each root item defines a collection, the ID of which is the ID of the
root item.  The components following the type are as follows:

    public_key - the public key of the collection owner.

    salt - a cryptographic-quality random byte string.

    sig - signature by the collection owner.

The public_key and sig are canonical s-expressions.

["kv" cn key value seq sig]

A kv item defines a key-value pair.  The components following the type
are as follows:

    cn - the ID of the collection to which the item belongs.

    key - a list of one or more possibly empty byte strings.

    value - a byte string of arbitrary length.

    seq - a sequence number, expressed in decimal.  This is a positive
    integer greater than the sequence numbers of any other items with
    the same key present in the local copy of the collection when this
    item was originally created.

    sig - signature by the collection owner.

The key and sig are canonical s-expressions.

["kv1" cn key value seq creator sig]

A kv1 item is similar to a kv item, except for the last two
components:

    creator - ID of a "member item" (see below) whose value is a
    public key, encoded as a canonical s-expression.  The member item
    need not be in the same collection.

    sig - signature by the identity specified in the creator item.

["kv0" cn key value seq sig]

A kv0 item is similar to a kv item, except that the signature is by
the public key specified in the item's value field.  In other words,
kv0 items are self-signed.  They are accepted only in highly specific
circumstances described later (for "guest member items", when these
are permitted).

    sig - signature by the identity specified in this same item.

We call kv, kv1, and kv0 items collectively key-value items.  This
scheme be understood in stages, starting with root and kv items, and
then adding in kv1 items, and then finally kv0 items (which are much
less important).

kv1 items utilize an authorization scheme where the collection owner
or somebody authorized directly or indirectly by the collection owner
grants particular rights to add items to the collection to various
groups and roles.  A group is defined by a collection.

A member item is a key-value item where the first component of the key
is the string "member".  A valid member item nominates a member of the
group defined by the collection in which the member item is contained.
To be valid, a member item must have a value that is a canonical
s-expression encoding a public key, and its key must have precisely
three elements:

    1. the string 'member',
    2. a string denoting the member's role,
    3. the fingerprint of the member's public key.

The item's value may be empty to indicate that the membership has been
revoked.  If the role is the empty string, we say that the item refers
to a guest member.

A rights item is a key-value item where the first component of the key
is the string "rights".  A valid rights item grants rights to a
particular group and role.  To be valid, a rights item must have a
value of "1", and the key must have at least four elements:

    1. the string 'rights',
    2. a group ID (a collection ID identifying the group),
    3. a role,
    4. a rights keyword.

We call the key suffix from the fourth element onwards a rights
specification, the meaning of which is determined by the rights
keyword (its first element).  The keywords 'put' and 'post' indicate
that the following elements represent a key prefix limiting the keys
to which members are permitted to put or post, respectively.

The value of a rights item can be "0" to indicate that the rights have
been revoked, or it can be the empty string to indicate that the
rights have been revoked retroactively.

Key-value items other than member items and rights items represent
application data.

A kv1 item is considered to be authorized only if sufficient rights
have been granted to the group and role of the creating member.
Furthermore, the membership must be current.

As a special case, a guest member item (a member item where the role
is the empty string) may be self-signed as a kv0 item if any rights at
all have been granted to guest members by this same collection.  This
is the only circumstance in which a kv0 item is considered to be
authorized.

In storing all these different kinds of items in a database, we have
found it convenient to view them as special cases of a universal item
type with a larger number of fields: type, cn, key, value, seq, salt,
creator, and sig.  For key-value items, the salt is empty.  For kv
items, the value of the creator field is the collection ID.  For kv0
items, it is the item ID.  For root items, the fields are filled in as
follows:

    type - "root".
    cn - the item ID.
    key - the empty list.
    value - the owner's public key.
    seq - "1".
    salt - random byte string.
    creator - the item ID.
    sig - signature by the owner.
'''

import hashlib
from os import urandom

from fusion.lib.sexp import encode, decode
from fusion.core.identity import decode_identity
from fusion.core.signature import decode_signature

def init_doctest():
    '''
    Initialize variables referred to in the doctests.
    '''
    from fusion.core.identity import generate_identity

    global identity, root, kv, kv_new
    identity = generate_identity()
    root = create_root_item(identity)
    kv = create_kv_item(root.id, ['favorite', 'color'], 'blue', 1, identity)
    kv_new = create_kv_item(
        root.id, ['favorite', 'color'], 'violet', 2, identity)

    global identity2, root2, rights
    identity2 = generate_identity()
    root2 = create_root_item(identity2)
    rights = create_kv_item(
        root.id, ['rights', root2.id, 'admin', 'put'], '1', 1, identity)

    global identity3, member, kv1
    identity3 = generate_identity()
    member = create_kv_item(
        root2.id, ['member', 'admin', identity3.get_fingerprint()],
        identity3.encode_public(), 1, identity2)
    kv1 = create_kv1_item(root.id, ['answer'], '42', 1, member.id, identity3)

    global guest_rights, identity4, guest_member, guest_kv1
    guest_rights = create_kv_item(
        root.id, ['rights', root.id, '', 'put', 'greeting'], '1', 1, identity)
    identity4 = generate_identity()
    guest_member = create_kv0_item(
        root.id, ['member', '', identity4.get_fingerprint()],
        identity4.encode_public(), 1, identity4)
    guest_kv1 = create_kv1_item(
        root.id, ['greeting'], 'hello', 1, guest_member.id, identity4)

class ItemBase(object):
    def __init__(self, type):
        self.type = type
        self._id = None         # Cached value

    def __cmp__(self, other):
        '''
        >>> kv < kv_new
        True
        >>> cmp(root, root)
        0
        '''
        return cmp(self.seq, other.seq) or cmp(self.id, other.id)

    @property
    def id(self):
        '''
        >>> len(root.id)
        20
        '''
        if self._id is None:
            self._id = self.get_digest(include_signature=True)

        return self._id

    def is_root(self):
        '''
        >>> root.is_root()
        True
        '''
        return self.type == 'root'

    def is_rights(self):
        '''
        >>> rights.is_rights()
        True
        '''
        return self.key and self.key[0] == 'rights'

    def is_member(self):
        '''
        >>> member.is_member()
        True
        >>> guest_member.is_member()
        True
        '''
        return self.key and self.key[0] == 'member'

    def is_guest_member(self):
        '''
        >>> member.is_guest_member()
        False
        >>> guest_member.is_guest_member()
        True
        '''
        try:
            type, role, fingerprint = self.key
            return type == 'member' and role == ''
        except ValueError:
            return False

    def validate(self):
        for field, type in ((self.cn, str),
                            (self.key, list),
                            (self.value, str),
                            (self.seq, int),
                            (self.salt, str),
                            (self.creator, str),
                            (self.sig, str)):
            if not isinstance(field, type):
                raise ValueError

        if not all(isinstance(part, str) for part in self.key):
            raise ValueError

        if self.seq < 1:
            raise ValueError

    def get_identity(self):
        if self.is_root() or self.is_member():
            return decode_identity(self.value)
        else:
            raise ValueError

    def get_signature(self):
        return decode_signature(self.sig)

    def verify_signature(self, signing_item):
        '''
        >>> root.verify_signature(root)
        True
        >>> kv.verify_signature(root)
        True
        >>> kv1.verify_signature(member)
        True
        >>> guest_member.verify_signature(guest_member)
        True
        '''
        # As a convenience, we enable the caller to pass the value
        # returned by get_item() without checking it:
        if signing_item is None:
            return False

        assert signing_item.id == self.creator

        try:
            ident = signing_item.get_identity()
            sig = self.get_signature()
            return ident.verify(self.get_digest(), sig)
        except ValueError:
            return False

    def get_digest(self, include_signature=False):
        sexp = self.encode(omit_signature = not include_signature)
        return hashlib.sha1(sexp).digest()

class Root(ItemBase):
    def __init__(self, public_key, salt, sig):
        ItemBase.__init__(self, 'root')
        self.value = public_key
        self.salt = salt
        self.sig = sig

    key = []
    seq = 1

    @property
    def cn(self):
        return self.id

    @property
    def creator(self):
        return self.id

    def validate(self):
        ItemBase.validate(self)

        decode_identity(self.value) # XXX Check strength?

        if not self.salt:
            raise ValueError

    def encode(self, omit_signature=False):
        data = [self.type,
                self.value,
                self.salt,
                self.sig]

        if omit_signature:
            del data[-1]

        return encode(data)

class KVBase(ItemBase):
    def __init__(self, type, cn, key, value, seq, sig):
        ItemBase.__init__(self, type)
        self.cn = cn
        self.key = key
        self.value = value
        self.seq = seq
        self.sig = sig

    salt = ''

    def validate(self):
        ItemBase.validate(self)

        if not self.key:
            raise ValueError

        if self.is_member():
            type, role, fingerprint = self.key
            if self.value:
                decode_identity(self.value) # XXX Check strength?
                if fingerprint != hashlib.sha1(self.value).digest():
                    raise ValueError
        elif self.is_rights():
            if len(self.key) < 4:
                raise ValueError
            if self.value not in ('1', '0', ''):
                raise ValueError

    def encode(self, omit_signature=False):
        data = [self.type,
                self.cn,
                encode(self.key),
                self.value,
                str(self.seq),
                self.sig]

        if omit_signature:
            del data[-1]

        return encode(data)

class KV(KVBase):
    def __init__(self, cn, key, value, seq, sig):
        KVBase.__init__(self, 'kv', cn, key, value, seq, sig)

    @property
    def creator(self):
        return self.cn

class KV0(KVBase):
    def __init__(self, cn, key, value, seq, sig):
        KVBase.__init__(self, 'kv0', cn, key, value, seq, sig)

    @property
    def creator(self):
        return self.id

    def validate(self):
        KVBase.validate(self)
        if not self.is_guest_member():
            raise ValueError

class KV1(KVBase):
    def __init__(self, cn, key, value, seq, creator, sig):
        KVBase.__init__(self, 'kv1', cn, key, value, seq, sig)
        self.creator = creator

    def validate(self):
        KVBase.validate(self)
        if self.creator == self.id or self.creator == self.cn:
            raise ValueError

    def encode(self, omit_signature=False):
        data = [self.type,
                self.cn,
                encode(self.key),
                self.value,
                str(self.seq),
                self.creator,
                self.sig]

        if omit_signature:
            del data[-1]

        return encode(data)

def create_root_item(identity):
    public_key = identity.encode_public()
    salt = urandom(20)
    item = Root(public_key, salt, None)
    sig = identity.sign(item.get_digest())
    item.sig = sig.encode()
    item.validate()
    return item

def create_kv_item(cn, key, value, seq, identity):
    item = KV(cn, key, value, seq, None)
    sig = identity.sign(item.get_digest())
    item.sig = sig.encode()
    item.validate()
    return item

def create_kv0_item(cn, key, value, seq, identity):
    item = KV0(cn, key, value, seq, None)
    sig = identity.sign(item.get_digest())
    item.sig = sig.encode()
    item.validate()
    return item

def create_kv1_item(cn, key, value, seq, creator, identity):
    item = KV1(cn, key, value, seq, creator, None)
    sig = identity.sign(item.get_digest())
    item.sig = sig.encode()
    item.validate()
    return item

def decode_item(string):
    '''
    >>> decode_item(root.encode()) == root
    True
    >>> decode_item(kv.encode()) == kv
    True
    >>> decode_item(kv1.encode()) == kv1
    True
    >>> decode_item(guest_member.encode()) == guest_member
    True
    '''
    data = decode(string)
    if not data or not all(isinstance(field, str) for field in data):
        raise ValueError

    type = data.pop(0)
    if type == 'root':
        item = Root(*data)
    elif type == 'kv':
        cn, key, value, seq, sig = data
        key = decode(key)
        seq = int(seq)
        item = KV(cn, key, value, seq, sig)
    elif type == 'kv0':
        cn, key, value, seq, sig = data
        key = decode(key)
        seq = int(seq)
        item = KV0(cn, key, value, seq, sig)
    elif type == 'kv1':
        cn, key, value, seq, creator, sig = data
        key = decode(key)
        seq = int(seq)
        item = KV1(cn, key, value, seq, creator, sig)
    else:
        raise ValueError

    item.validate()
    return item

def item_from_row(row):
    '''
    Construct an Item from a database row.

    This function is specific to the "items" sqlite table defined in
    fusion.db.sqlite_db.

    >>> item_from_row(row_from_item(root)) == root
    True
    >>> item_from_row(row_from_item(kv)) == kv
    True
    >>> item_from_row(row_from_item(kv1)) == kv1
    True
    >>> item_from_row(row_from_item(guest_member)) == guest_member
    True
    '''
    num, id, type, cn, key, value, size, seq, salt, creator, sig = row

    assert len(value) == size

    id = str(id)
    type = str(type)
    cn = str(cn)
    key = decode(str(key))
    value = str(value)
    seq = int(seq)
    salt = str(salt)
    creator = str(creator)
    sig = str(sig)

    if type == 'root':
        item = Root(value, salt, sig)
    elif type == 'kv':
        item = KV(cn, key, value, seq, sig)
    elif type == 'kv0':
        item = KV0(cn, key, value, seq, sig)
    elif type == 'kv1':
        item = KV1(cn, key, value, seq, creator, sig)
    else:
        raise ValueError

    item.validate()

    assert item.id == id
    assert item.type == type
    assert item.cn == cn
    assert item.key == key
    assert item.value == value
    assert item.seq == seq
    assert item.salt == salt
    assert item.creator == creator
    assert item.sig == sig

    item.num = num
    return item

def row_from_item(item):
    '''
    Generate a database row from an Item.

    This function is specific to the "items" sqlite table defined in
    fusion.db.sqlite_db.
    '''
    id = buffer(item.id)
    type = buffer(item.type)
    cn = buffer(item.cn)
    key = buffer(encode(item.key))
    value = buffer(item.value)
    seq = int(item.seq)
    salt = buffer(item.salt)
    creator = buffer(item.creator)
    sig = buffer(item.sig)

    return None, id, type, cn, key, value, len(value), seq, salt, creator, sig

if __name__ == "__main__":
    import doctest
    init_doctest()
    doctest.testmod()
